#include <iostream>
#include <vector>
#define INF INT_MAX / 2
using namespace std;
int main(void) {
    int vnums, arcnums;
    cout << "点数" << "边数" << endl;
    cin >> vnums >> arcnums;
    vector<vector<int>> adj(vnums, vector<int>(vnums, INF));
    vector<vector<int>> dist(vnums, vector<int>(vnums, INF)); // 任意两点最短距离
    vector<vector<int>> seq(vnums, vector<int>(vnums, 0)); // 记录最短路径
    vector<vector<int>> edges(arcnums, vector<int>(3, 0));
    // 弧尾 弧头 权值
    cout << "依次输入边" << endl;
    for (int i = 0; i < arcnums; ++i) {
        cout << "第" << i+1 << "条边" << endl;
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    // 把边录入邻接矩阵
    for (auto arc: edges) {
        adj[arc[0]][arc[1]] = arc[2];  // 有向图只写这一个就行
        dist[arc[0]][arc[1]] = arc[2];
        // adj[arc[1]][arc[0]] = arc[2]; // 无向图还要写这一行
    }
    // 初始化路径记录数组
    for (int i = 0; i < vnums; ++i) {
        for (int j = 0; j < vnums; ++j) {
            seq[i][j] = j;
        }
    }
    // 开始求最短路
    for (int mid = 0; mid < vnums; ++mid) {
        for (int begin = 0; begin < vnums; ++begin) {
            for (int end = 0; end < vnums; ++end) {
                if (begin != mid && end != mid && begin != end) {
                    if (adj[begin][mid] + adj[mid][end] < dist[begin][end]) {
                        dist[begin][end] = adj[begin][mid] + adj[mid][end];
                        seq[begin][end] = mid;
                    }
                }
            }
        }
    }
    // 输出测试数据结果
    cout << "dist" << endl;
    for (int r = 0; r < vnums; ++r) {
        for (int c = 0; c < vnums; ++c) {
            if (dist[r][c] != INF)
                cout << dist[r][c] << " ";
            else
                cout << "-" << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << "parent" << endl;
    for (int r = 0; r < vnums; ++r) {
        for (int c = 0; c < vnums; ++c) {
            cout << seq[r][c] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
// 测试数据
// 节点数 边数量 接下来的每一条边 开始节点
// 4 5  0 1 5  0 2 3  1 2 1  1 3 4  2 3 2   0
// 5 6  0 1 5  0 2 3  0 4 3  2 1 1  1 3 4  2 3 2  0